package demo1;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-08-31
 * Time: 8:36
 */
public class TestDemo {

    //将一个数拆分有多少种方法,其中拆出的数字的后面一定要比前面的数字大或者等于
    // 对于4这个数字来说
    // 1 1 1 1
    // 1 1 2
    // 2 2
    // 1 3
    // 4

    public static int ways1(int n){
        if(n==0) return 0;
        return  process(1,n);
    }
    //从pre=1开始尝试
    //rest时剩余的尝试步数
    public static int process(int prev,int rest){
        if(rest==0){
            //剩余的尝试数字为0,而且前面的是符合条件的说明我有一种方法
            //这种情况也把单独的数字包含进去了  比如拆4-----> 拆分成4(prev : 4 rest :0)
            return 1;
        }
        if(prev>rest){
            //如果尝试的数字大于剩余的尝试数字,那么不合法,方法为0
            return 0;
        }
        //下面的情况就是prev <=rest的情况了
        int ways = 0;
        //这里其实也就限制了prev<=first
        //这里包含等于rest情况--->也就包含了拆分成一个数字的情况
        for(int first = prev;first<=rest;++first){
            //比如拆分4     f  p
            // 1  3  ----> 1 ,2--->合法
            //             2 ,1--->不合法
            //             3 ,0--->合法
            //选择当前的数字,剩余的数字就是rest-当前数字
            ways += process(first,rest - first);
        }
        return ways;
    }

    //改为动态规划
    public static int ways2(int n){
        int[][] dp = new int[n+1][n+1];
        //填格子
        for(int prev = 0;prev<=n;++prev){
            dp[prev][0] = 1;
            dp[prev][prev] = 1;
        }
        //prev-->行
        for(int prev = n-1;prev>=1;--prev){
            //rest-->列
            for(int rest = prev +1;rest<=n;++rest){
                int ways = 0;
                for(int first = prev;first<=rest;++first){
                    ways += dp[first][rest - first];
                }
                dp[prev][rest] = ways;
            }
        }
        return dp[1][n];
    }

    public static int ways3(int n){
        int[][] dp = new int[n+1][n+1];
        //填格子
        for(int prev = 0;prev<=n;++prev){
            dp[prev][0] = 1;
            dp[prev][prev] = 1;
        }
        //prev-->行
        for(int prev = n-1;prev>=1;--prev){
            //rest-->列
            for(int rest = prev +1;rest<=n;++rest){
                dp[prev][rest] = dp[prev+1][rest] + dp[prev][rest-prev];
            }
        }
        return dp[1][n];
    }

    public static void main(String[] args) {
        System.out.println(ways1(10));
        System.out.println(ways2(10));
        System.out.println(ways3(10));
    }

}
